#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<queue>
#include<string.h>
#include<unordered_map>
using namespace std;

//typedef pair<int, int> PII;
//
//const int N = 410;
//
//
//int n, m, x, y,  dist[N][N];
//
//int dx[8] = { -2,-1,1,2,2,1,-1,-2 };
//int dy[8] = { 1,2,2,1,-1,-2,-2,-1 };
//
//
//
//int main()
//{
//	cin >> n >> m >> x >> y;
//	memset(dist, -1, sizeof dist);
//	queue<PII> q;
//	q.push({ x,y });
//	dist[x][y] = 0;
//	while (q.size())
//	{
//		PII t = q.front(); q.pop();
//		for (int k = 0; k < 8; k++)
//		{
//			int _x = t.first + dx[k],
//				_y = t.second + dy[k];
//
//			if (_x >= 1 && _x <= n && _y >= 1 && _y <= m
//				&& dist[_x][_y] == -1)
//			{
//				dist[_x][_y] = dist[t.first][t.second] + 1;
//				q.push({ _x,_y });
//			}
//		}
//	}
//
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			cout << dist[i][j] << " ";
//		}
//		cout << endl;
//	}
//
//	return 0;
//}

//typedef pair<int, int> PII;
//
//const int N = 40;
//char a[N][N];
//int f[N][N];
//
//int n, m, x, y, ret = INT_MAX, count;
//
//int dx[4] = { -1,1,0,0 };
//int dy[4] = { 0,0,-1,1 };
//
//void bfs()
//{
//    queue<PII> q;
//    f[x][y] = 0;
//    q.push({ x,y });
//    while (q.size())
//    {
//        PII t = q.front(); q.pop();
//        int i = t.first, j = t.second;
//        for (int k = 0; k < 4; k++)
//        {
//            int _x = i + dx[k], _y = j + dy[k];
//            if (_x >= 1 && _x <= n && _y >= 1 && _y <= m
//                && a[_x][_y] != '*' && f[_x][_y] == -1)
//            {
//                f[_x][_y] = f[i][j] + 1;
//                if (a[_x][_y] != 'e')
//                    q.push({ _x,_y });
//            }
//        }
//    }
//}
//
//
//
//int main()
//{
//    memset(f, -1, sizeof f);
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            cin >> a[i][j];
//            if (a[i][j] == 'k') x = i, y = j;
//        }
//    }
//    bfs();
//
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            if (a[i][j] == 'e' && f[i][j] != -1) count++, ret = min(ret, f[i][j]);
//
//
//        }
//    }
//
//    if (count == 0) cout << -1 << endl;
//    else cout << count << " " << ret << endl;
//
//    return 0;
//}

//const int N = 1e5 + 10;
//
//int dist[N];
//
//int t, x, y, n = 1e5;
//
//void bfs()
//{
//	queue<int> q;
//	q.push(x);
//	while (q.size())
//	{
//		auto t = q.front(); q.pop();
//		int a = t + 1, b = t - 1, c = t * 2;
//		if (a <= n && dist[a] == -1) dist[a] = dist[t] + 1,q.push(a);
//		if (b > 0 && dist[b] == -1) dist[b] = dist[t] + 1, q.push(b);
//		if (c <= n && dist[c] == -1) dist[c] = dist[t] + 1, q.push(c);
//
//		if (a == y || b == y || c == y)
//		{
//			return;
//		}
//
//	}
//}
//
//
//int main()
//{
//	cin >> t;
//	while (t--)
//	{
//		cin >> x >> y;
//		memset(dist, -1, sizeof dist);
//		dist[x] = 0;
//		bfs();
//		cout << dist[y] << endl;
//	}
//	return 0;
//}

//unordered_map<string, int> dist;
//
//string ret = "123804765";
//
//string s;
//
//int dx[4] = { -1,1,0,0 };
//int dy[4] = { 0,0,-1,1 };
//
//void bfs()
//{
//	queue<string> q;
//	q.push(s);
//	dist.insert({ s,0 });
//	while (q.size())
//	{
//		string t = q.front();  q.pop();
//		auto pos = t.find('0'), x = pos / 3, y = pos % 3;
//		for (int k = 0; k < 4; k++)
//		{
//			int _x = x + dx[k], _y = y + dy[k],
//				pos1 = 3 * _x + _y;
//
//			if (_x >= 0 && _x < 3 && _y >= 0 && _y < 3 && pos1 < 9)
//			{
//				string tmp = t;
//				swap(tmp[pos1], tmp[pos]);
//				if (dist.find(tmp) != dist.end())
//					continue;
//				q.push(tmp);
//				dist[tmp] = dist[t] + 1;
//				if (tmp == ret) return;
//				
//			}
//
//		}
//	}
//}
//
//int main()
//{
//	cin >> s;
//	bfs();
//	cout << dist[ret] << endl;
//	return 0;
//}


//const int N = 1e3 + 10;
//
//
//typedef pair<int, int> PII;
//
//char a[N][N];
//int dist[N][N];
//int n, m;
//
//int dx[4] = { 1,-1,0,0 };
//int dy[4] = { 0,0,1,-1 };
//
//void bfs()
//{
//    memset(dist, -1, sizeof dist);
//    queue<PII> q;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            if (a[i][j] == '1')
//            {
//                q.push({ i,j });
//                dist[i][j] = 0;
//            }
//        }
//    }
//
//    while (q.size())
//    {
//        auto t = q.front(); q.pop();
//        int x = t.first, y = t.second;
//        for (int i = 0; i < 4; i++)
//        {
//            int _x = x + dx[i], _y = y + dy[i];
//            if (_x >= 1 && _x <= n && _y >= 1
//                && _y <= m && dist[_x][_y] == -1)
//            {
//                dist[_x][_y] = dist[x][y] + 1;
//                q.push({ _x,_y });
//            }
//
//        }
//    }
//
//}
//
//
//int main()
//{
//    cin >> n >> m;
//
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            cin >> a[i][j];
//        }
//    }
//
//    bfs();
//
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            cout << dist[i][j] << " ";
//        }
//        cout << endl;
//    }
//
//    return 0;
//}